Typically, when a user misspells a search query, the search engine provider compares the misspelled search query with frequently encountered misspelled search queries stored in a query log. In turn, the frequently encountered misspelled search queries are associated with their correctly spelled search query counterparts in the query log. If the misspelled search query matches one of the frequently encountered misspelled search queries in the query log, the misspelled search query is associated with the correctly spelled search query counterpart, and a set of search suggestions is returned to the user. This method works fairly well with commonly misspelled search queries whether they are complete search queries or portions of search queries. However, this process fails to correct search queries with misspellings that are not in the query log. The result is a loss of opportunity in presenting the user with potentially relevant search suggestions that would have been delivered if the misspelling had not occurred.